package vip.zhenzicheng.algorithm.leetcode.binary_tree;

import vip.zhenzicheng.algorithm.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/path-sum-iii/">路径总和 III [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-07-01 10:41
 */
public class ConvertSortedListToBinarySearchTree_109 {

  public int pathSum(TreeNode root, int targetSum) {
    /*key:前缀和,value:出现次数*/
    Map<Integer, Integer> prefixSum = new HashMap<>();
    // 防止target就等于当前节点值并且前缀和0，即当前节点就是一个解，所以保存一个0的起始次数
    prefixSum.put(0, 1); // 前缀和0出现1次

    return traversal(root, 0, targetSum, prefixSum); // 根节点开始遍历
  }

  public int traversal(TreeNode root, int curSum, int target, Map<Integer, Integer> prefixSum) {
    if (root == null) {
      return 0;
    }

    curSum = curSum + root.val; // 计算当前节点的前缀和
    // 当前节点的前缀和是否满足题解，记录满足条件的路径数
    int result = prefixSum.getOrDefault(curSum - target, 0);
    // 保存当前前缀和以及出现的次数，如果没出现过就默认是1次
    prefixSum.put(curSum, prefixSum.getOrDefault(curSum, 0) + 1);
    // 向下递归找左右子树中满足条件的节点
    result = result + traversal(root.left, curSum, target, prefixSum) + traversal(root.right, curSum, target, prefixSum);
    // 一个节点的前缀和只对当前节点的子节点有效，向上返回要-1
    prefixSum.put(curSum, prefixSum.get(curSum) - 1);
    return result;
  }
}
